Random number generation is an important ingredient to many cryptographic algorithms. For example, random numbers are needed to produce nonces, keys, including session keys, etc. Also random numbers may be needed to control cryptographic algorithms themselves. One type of cryptographic algorithms that need an especially large number of random numbers are so-called stream ciphers. In a stream cipher a stream of plain text is encrypted by combining it with a stream of random numbers; typically the two streams are XOR-ed together. It is preferred not to make statistical assumptions about the stream of plain text, which means that the stream of random numbers must be especially resilient to attack; in particular since a large amount of it may be available to the attacker. It is understood that when referring to generated random numbers not true but pseudo random numbers are meant.
Random numbers are also used outside the field of cryptography. For example, random numbers are used in statistics. Also simulations may use random numbers to model the unpredictability of real world events. However the demands placed on random numbers in the field of cryptography differ from those outside that field. In cryptography, security is of overriding importance. Both cryptography and statistics prefer that the generated random numbers are indistinguishable from true random numbers. However, the approach to this differs. In statistics and related fields it is sufficient that no relevant statistical test can detect a difference between the two streams. However, in cryptography it must be assumed that an attacker is willing to invest significant computational resources in investigating the presumed random numbers. For example, an attacker may be interested in predicting future values from past values.
A stream of random numbers to be used in cryptography may preferably be generated fast yet require low resources; say a small smart card or RFID chip. At the same time it must be secure against an attacker willing to invest a disproportional amount of computation. These conflicting demands have produced many proposed designs.
For example, one type of random number generator is the so-called linear shift register. A linear shift register produces a sequence of bits. A next bit in the sequence is computed by calculating a fixed combination of selected previous bits in the sequence. Linear shift registers have long periods, relatively good statistical properties and are fast using low resources. Unfortunately, they are insecure in the face of cryptographic attack: the so-called Berlekamp-Massey algorithm may be used to attack the stream.
The book chapter by James E Gentle: “Chapter 1. Simulating Random Numbers from a Uniform Distribution”, In: “Random Number Generation and Monte Carlos Methods (Second Edition)”, 1 Jan. 2005 (2005 Jan. 1), Springer, New York, XP055082923, ISBN: 978-0-38-700178-4, pages 1-56, discloses several prior art solutions. It describes in Section 1.8, page 46, that random number generations can often be improved by combining more than one generator, and that the generators that are combined can be of any type. It also describes a combined generator that uses a linear congruentiaql generator and two shift register generators.
An improvement came from taking two independently generated linear shift register sequences and combining them in some non-linear way. Examples of this approach are the so-called shrinking generator or the alternating step generator. The idea being that having two independent linear shift registers doubles the number of parameters that must be determined to attack the sequences; moreover two unrelated sets of parameters must somehow be deduced from a single stream in which their effects are mixed up.
Indeed, it turns out that the combination of two independent sequences generated by linear shift registers indeed increases the difficulty of cryptographic attack. Such attacks nevertheless remain possible however, although they require a larger amount of random numbers to work from. There thus remains a need for improved random number generators.